Fermat's Theorem
What is Fermat's Little Theorem?
Fermat's Little Theorem is a fundamental principle in number theory that states if p is prime and a is not divisible by p, then a^(p-1) ≡ 1 (mod p). It's a powerful tool used in cryptography, particularly for primality testing and modular arithmetic calculations.
Key Components:
1. Prime number p
2. Integer a (coprime to p)
3. Modular arithmetic
4. Power relationship
Two Main Forms:
1. If gcd(a,p) = 1: a^(p-1) ≡ 1 (mod p)
2. For any a: a^p ≡ a (mod p)
Examples:
Example 1:
fined 7^2021 mod 13
• 13 is prime and gcd(7,13) = 1
• Then 7^12 ≡ 1 (mod 13)
Step 1: Divide 2021 by 12
• 2021 = 168 × 12 + 5
• Therefore, 7^2021 = 7^(168×12 + 5)
• = (7^12)^168 × 7^5
Step 2: Using Fermat's Theorem
• 7^12 ≡ 1 (mod 13)
• (7^12)^168 ≡ 1^168 ≡ 1 (mod 13)
Step 3: Calculate 7^5 mod 13
• 7^1 ≡ 7 (mod 13)
• 7^2 ≡ 49 ≡ 10 (mod 13)
• 7^3 ≡ 7 × 10 ≡ 70 ≡ 5 (mod 13)
• 7^4 ≡ 5 × 7 ≡ 35 ≡ 9 (mod 13)
• 7^5 ≡ 9 × 7 ≡ 63 ≡ 11 (mod 13)
Final Result:
• 7^2021 ≡ (7^12)^168 × 7^5 ≡ 1 × 11 ≡ 11 (mod 13)
• Therefore, 7^2021 ≡ 11 (mod 13)
Example 2:
Let p = 5, a = 2
• 2^4 = 16 ≡ 1 (mod 5), Process:
• 2^4 = 16
• 16 ÷ 5 = 3 remainder 1
• Therefore, 2^4 ≡ 1 (mod 5)
Example 3:
Let p = 7, a = 3
• 3^6 = 729 ≡ 1 (mod 7), Process:
• 3^6 = 729
• 729 ÷ 7 = 104 remainder 1
• Therefore, 3^6 ≡ 1 (mod 7)